#include <stdio.h>
#include <stdlib.h>

typedef int ElementType; // 元素类型

//队列节点结构体
typedef struct QueueNode{
    ElementType data;          //数据域
    struct QueueNode *next;     //指针域
}QueueNode;

//队头和队尾指针
typedef struct {
    QueueNode *front;
    QueueNode *rear;
}Queue;

//初始化
Queue* initQueue(){
    Queue *q = (Queue*)malloc(sizeof(Queue));
    QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode));
    node->data = 0;
    node->next = NULL; // 头节点没有指向任何元素，空队列
    q->front = node;  // 队头和队尾指针指向头节点。可用于判断是否空队列
    q->rear = node;
    return q;
}

// 判断队列是否为空
int isEmpty(Queue *q){
    if(q->front==q->rear){
        printf("空队列\n");
        return 0;
    }
    else{
        return 1;
    }
}

//入队（尾插法）
void equeue(Queue *q, ElementType e){
    QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode)); // 创建插入节点，分配内存
    node -> data = e;
    printf("已插入元素：%d\n",e);
    node -> next = NULL; //插入节点成为新尾节点，尾节点next指向空。
    q->rear->next = node;  //让当前队尾节点（q->rear）的next指针指向新节点，将新节点接入队列
    q->rear = node; //将队尾指针（q->rear）移动到新节点，使新节点成为新的队尾
}

// 出队
int dequeue(Queue *q, ElementType *e){
    if(!isEmpty(q))
    {
        printf("空队列");
        return 0;
    }
    QueueNode *node = q->front->next; // 新建指针存储被删节点，注意队列是队头出队。
    *e = node->data;      // 记录出队元素的数据
    printf("已出队元素：%d\n",*e);
    q->front->next = node->next;    // 把队头接到被删节点的后一个节点
    if(q->rear == node){    
        q->rear = q->front;    //如果出队的是队尾，也就是最后一个节点，则让队头等于队尾，意为空队列
    }
    free(node);  //释放出队节点内存
    return 1;
}

//获取队头元素
int getfront(Queue *q){
    if(!isEmpty(q))
    {
        printf("空队列");
        return 0;
    }
    return q->front->next->data; // 因为队头指向的是头节点不是首节点，所以要这么写。
}

int main(){
    Queue *node = initQueue();
    equeue(node, 10);
    equeue(node, 20);
    equeue(node, 30);
    getfront(node);
    printf("队头元素为：%d\n",getfront(node));
    int a;
    dequeue(node, &a);
    dequeue(node, &a);
    return 0;
}